package offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class offer_0038 {
    public String[] permutation(String s) {
        char[] list=s.toCharArray();
        int len=list.length;
        List<String> result=new LinkedList<>();
        List<Character> path=new ArrayList<>();
        boolean[] flag=new boolean[len];
        dp(result,path,len,list,flag);
        len=result.size();
        String[] result2=new String[len];
        for(int i=0;i<len;++i){
            result2[i]=result.get(i);
        }
        return result2;
    }
    public void dp(List<String> result,List<Character> path,int len,char[] list,boolean[] flag){
        if(path.size()==len){
            String s="";
            for(int i=0;i<len;++i){
                s+=path.get(i);
            }
            result.add(s);
            return;
        }
        for(int i=0;i<len;++i){
            if(!flag[i]&&search(i,list,flag)){
                path.add(list[i]);
                flag[i]=true;
                dp(result,path,len,list,flag);
                flag[i]=false;
                path.remove(path.size()-1);
            }
        }
    }
    public boolean search(int index,char[] list,boolean[] flag){
        for(int i=0;i<index;++i){
            if(list[i]==list[index]&&flag[i]) return false;
        }
        return true;
    }
}
